\relax 
\providecommand\hyper@newdestlabel[2]{}
\providecommand\HyperFirstAtBeginDocument{\AtBeginDocument}
\HyperFirstAtBeginDocument{\ifx\hyper@anchor\@undefined
\global\let\oldcontentsline\contentsline
\gdef\contentsline#1#2#3#4{\oldcontentsline{#1}{#2}{#3}}
\global\let\oldnewlabel\newlabel
\gdef\newlabel#1#2{\newlabelxx{#1}#2}
\gdef\newlabelxx#1#2#3#4#5#6{\oldnewlabel{#1}{{#2}{#3}}}
\AtEndDocument{\ifx\hyper@anchor\@undefined
\let\contentsline\oldcontentsline
\let\newlabel\oldnewlabel
\fi}
\fi}
\global\let\hyper@last\relax 
\gdef\HyperFirstAtBeginDocument#1{#1}
\providecommand\HyField@AuxAddToFields[1]{}
\providecommand\HyField@AuxAddToCoFields[2]{}
\@writefile{toc}{\contentsline {chapter}{Abstract}{i}{dummy.2}}
\@writefile{toc}{\vspace  {1em}}
\@writefile{toc}{\contentsline {chapter}{Acknowledgements}{ii}{dummy.3}}
\@writefile{toc}{\vspace  {1em}}
\@writefile{toc}{\contentsline {chapter}{Contents}{iii}{dummy.4}}
\@writefile{toc}{\contentsline {chapter}{List of Figures}{v}{dummy.6}}
\gdef \LT@i {\LT@entry 
    {1}{65.71553pt}\LT@entry 
    {1}{317.62683pt}}
\@writefile{toc}{\contentsline {chapter}{Abbreviations}{vi}{dummy.8}}
\citation{5365034}
\@writefile{toc}{\vspace  {2em}}
\@writefile{toc}{\contentsline {chapter}{\numberline {1}Introduction}{1}{chapter.11}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{Chapter1}{{1}{1}{Introduction}{chapter.11}{}}
\@writefile{toc}{\contentsline {section}{\numberline {1.1}Radio Astronomy}{1}{section.12}}
\@writefile{toc}{\contentsline {section}{\numberline {1.2}SKA and South Africa}{1}{section.13}}
\citation{954501}
\citation{5536972}
\@writefile{toc}{\contentsline {section}{\numberline {1.3}Compression Scheme Chosen}{2}{section.14}}
\@writefile{toc}{\contentsline {section}{\numberline {1.4}Research Questions}{2}{section.15}}
\@writefile{toc}{\contentsline {section}{\numberline {1.5}Report Structure}{3}{section.19}}
\citation{6530082}
\@writefile{toc}{\contentsline {chapter}{\numberline {2}Background}{4}{chapter.20}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{Chapter2}{{2}{4}{Background}{chapter.20}{}}
\@writefile{toc}{\contentsline {section}{\numberline {2.1}Square Kilometer Array in South Africa}{4}{section.21}}
\@writefile{lof}{\contentsline {figure}{\numberline {2.1}{\ignorespaces SKA MeerKAT Pipeline}}{4}{figure.caption.22}}
\providecommand*\caption@xref[2]{\@setref\relax\@undefined{#1}}
\newlabel{fig:MeerKAT Pipeline}{{2.1}{4}{SKA MeerKAT Pipeline}{figure.caption.22}{}}
\citation{salomon2004data}
\citation{1514415}
\@writefile{toc}{\contentsline {section}{\numberline {2.2}Compression Schemes}{5}{section.23}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2.1}Basic Methods}{5}{subsection.24}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2.2}Statistical Methods}{5}{subsection.25}}
\citation{6196449}
\citation{613235}
\citation{5974482}
\citation{488381}
\citation{5164745}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2.3}Transformations}{6}{subsection.26}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.2.4}Dictionary Methods}{6}{subsection.27}}
\@writefile{toc}{\contentsline {section}{\numberline {2.3}Entropy Encoders}{6}{section.28}}
\citation{5365034}
\citation{5536972}
\@writefile{toc}{\contentsline {section}{\numberline {2.4}Huffman Coding Overview}{7}{section.29}}
\@writefile{lof}{\contentsline {figure}{\numberline {2.2}{\ignorespaces Tree showing the first step of ABRACADABRA compression}}{8}{figure.caption.30}}
\newlabel{fig:Huffman Tree 1}{{2.2}{8}{Tree showing the first step of ABRACADABRA compression}{figure.caption.30}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {2.3}{\ignorespaces Tree showing the second step of ABRACADABRA compression}}{8}{figure.caption.31}}
\newlabel{fig:Huffman Tree 2}{{2.3}{8}{Tree showing the second step of ABRACADABRA compression}{figure.caption.31}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {2.4}{\ignorespaces Tree showing the second step of ABRACADABRA compression}}{9}{figure.caption.32}}
\newlabel{fig:Huffman Tree 3}{{2.4}{9}{Tree showing the second step of ABRACADABRA compression}{figure.caption.32}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {2.5}{\ignorespaces Tree showing the second step of ABRACADABRA compression}}{9}{figure.caption.32}}
\newlabel{fig:Huffman Tree 4}{{2.5}{9}{Tree showing the second step of ABRACADABRA compression}{figure.caption.32}{}}
\citation{5365034,1192978}
\@writefile{toc}{\contentsline {section}{\numberline {2.5}Huffman Coder Extensions}{10}{section.33}}
\@writefile{toc}{\contentsline {section}{\numberline {2.6}Parallelism}{10}{section.34}}
\citation{6339599}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.6.1}Parallelism via the CPU}{11}{subsection.35}}
\@writefile{toc}{\contentsline {subsection}{\numberline {2.6.2}Parallelism via the GPU}{11}{subsection.36}}
\citation{672291}
\@writefile{toc}{\contentsline {chapter}{\numberline {3}Design}{13}{chapter.37}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{Chapter3}{{3}{13}{Design}{chapter.37}{}}
\@writefile{toc}{\contentsline {section}{\numberline {3.1}Overview}{13}{section.38}}
\@writefile{toc}{\contentsline {section}{\numberline {3.2}Algorithms}{14}{section.39}}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2.1}Huffman Coding}{14}{subsection.40}}
\@writefile{lof}{\contentsline {figure}{\numberline {3.1}{\ignorespaces Pseudo Code for the Code generation method used by Huffman Coding}}{15}{figure.caption.41}}
\newlabel{sudoCode:codegeneration}{{3.1}{15}{Pseudo Code for the Code generation method used by Huffman Coding}{figure.caption.41}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {3.2}{\ignorespaces Pseudo code for the Huffman coding decompression method}}{15}{figure.caption.61}}
\newlabel{sudoCode:Decompression}{{3.2}{15}{Pseudo code for the Huffman coding decompression method}{figure.caption.61}{}}
\citation{HuffmanCodingSite}
\@writefile{toc}{\contentsline {subsection}{\numberline {3.2.2}Adaptive Huffman Coding}{16}{subsection.85}}
\@writefile{lof}{\contentsline {figure}{\numberline {3.3}{\ignorespaces Adaptive Huffman Coding Update Process}}{16}{figure.caption.86}}
\newlabel{fig:AHC Update procedure}{{3.3}{16}{Adaptive Huffman Coding Update Process}{figure.caption.86}{}}
\citation{blelloch1990prefix}
\@writefile{toc}{\contentsline {section}{\numberline {3.3}Prefix Sum}{17}{section.87}}
\@writefile{toc}{\contentsline {section}{\numberline {3.4}GPU based Huffman Coding}{18}{section.88}}
\@writefile{toc}{\contentsline {section}{\numberline {3.5}Benchmarking}{18}{section.89}}
\@writefile{toc}{\contentsline {chapter}{\numberline {4}Adaptive Huffman Implementation}{20}{chapter.90}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{Chapter4}{{4}{20}{Adaptive Huffman Implementation}{chapter.90}{}}
\@writefile{toc}{\contentsline {section}{\numberline {4.1}Tree Structure}{20}{section.91}}
\@writefile{toc}{\contentsline {section}{\numberline {4.2}Encoding Procedure}{20}{section.116}}
\@writefile{lof}{\contentsline {figure}{\numberline {4.1}{\ignorespaces Pseudo code for the Adaptive Huffman Coding Node class}}{21}{figure.caption.92}}
\newlabel{sudoCode:AHCNode}{{4.1}{21}{Pseudo code for the Adaptive Huffman Coding Node class}{figure.caption.92}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {4.2}{\ignorespaces Pseudo code for the Adaptive Huffman Coding algorithm's encoding procedure}}{22}{figure.caption.117}}
\newlabel{sudoCode:AHCEncoding}{{4.2}{22}{Pseudo code for the Adaptive Huffman Coding algorithm's encoding procedure}{figure.caption.117}{}}
\@writefile{toc}{\contentsline {section}{\numberline {4.3}Update Procedure}{22}{section.165}}
\@writefile{lof}{\contentsline {figure}{\numberline {4.3}{\ignorespaces Pseudo code for Adaptive Huffman Coding algorithm's updateNode method}}{23}{figure.caption.166}}
\newlabel{sudocode:updateAHC}{{4.3}{23}{Pseudo code for Adaptive Huffman Coding algorithm's updateNode method}{figure.caption.166}{}}
\@writefile{toc}{\contentsline {section}{\numberline {4.4}Feasibility of AHC}{23}{section.185}}
\@writefile{toc}{\contentsline {chapter}{\numberline {5}Huffman Coding Implementation}{24}{chapter.186}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{Chapter5}{{5}{24}{Huffman Coding Implementation}{chapter.186}{}}
\@writefile{toc}{\contentsline {section}{\numberline {5.1}CPU Only Huffman Coding}{24}{section.187}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1.1}Binning}{24}{subsection.188}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.1}{\ignorespaces Pseudo code for the Huffman Coding binning method}}{25}{figure.caption.189}}
\newlabel{sudocode:binning}{{5.1}{25}{Pseudo code for the Huffman Coding binning method}{figure.caption.189}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1.2}Tree Construction and Code Generation}{25}{subsection.203}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.2}{\ignorespaces Pseudo code for the Huffman Coding Generate Tree Method}}{25}{figure.caption.204}}
\newlabel{sudocode:generateTree}{{5.2}{25}{Pseudo code for the Huffman Coding Generate Tree Method}{figure.caption.204}{}}
\citation{O'Neil:2011:FDC:1964179.1964189}
\citation{O'Neil:2011:FDC:1964179.1964189}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1.3}Float-to-code swapping procedure}{26}{subsection.233}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.3}{\ignorespaces Pseudo code for the Huffman Coding Swap Values method}}{26}{figure.caption.234}}
\newlabel{sudocode:swapvalues}{{5.3}{26}{Pseudo code for the Huffman Coding Swap Values method}{figure.caption.234}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1.4}Binary Sequence to Char conversion}{26}{subsection.262}}
\citation{blelloch1990prefix}
\@writefile{lof}{\contentsline {figure}{\numberline {5.4}{\ignorespaces Pseudo code for the Huffman Coding Dynamic programming Char Conversion method}}{27}{figure.caption.263}}
\newlabel{sudoCode:dynamiccharconversion}{{5.4}{27}{Pseudo code for the Huffman Coding Dynamic programming Char Conversion method}{figure.caption.263}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.1.5}Decompression}{27}{subsection.328}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.5}{\ignorespaces Pseudo code for the Prefix Sum version of the Huffman Coding char conversion method}}{28}{figure.caption.287}}
\newlabel{sudoCode:prefixlinear}{{5.5}{28}{Pseudo code for the Prefix Sum version of the Huffman Coding char conversion method}{figure.caption.287}{}}
\@writefile{toc}{\contentsline {section}{\numberline {5.2}GPU and CPU combined Huffman Scheme}{28}{section.329}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.6}{\ignorespaces Pseudo code for the Thrust binning method}}{29}{figure.caption.331}}
\newlabel{sudocode:charconvgpu}{{5.6}{29}{Pseudo code for the Thrust binning method}{figure.caption.331}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2.1}Binning}{29}{subsection.330}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2.2}Symbol to Code Swapping}{30}{subsection.354}}
\citation{blelloch1990prefix}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2.3}Binary sequence to Character array conversion}{31}{subsection.355}}
\@writefile{toc}{\contentsline {subsection}{\numberline {5.2.4}Feasibility of Huffman Coding}{31}{subsection.392}}
\@writefile{lof}{\contentsline {figure}{\numberline {5.7}{\ignorespaces Pseudo code for the Thrust version of the Prefix sum char conversion}}{32}{figure.caption.356}}
\newlabel{sudocode:thrustprefix}{{5.7}{32}{Pseudo code for the Thrust version of the Prefix sum char conversion}{figure.caption.356}{}}
\@writefile{toc}{\contentsline {chapter}{\numberline {6}Results}{33}{chapter.393}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{Chapter6}{{6}{33}{Results}{chapter.393}{}}
\@writefile{toc}{\contentsline {section}{\numberline {6.1}Tests}{33}{section.394}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.1.1}Feasibility of Huffman Coding in parallel}{33}{subsection.395}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.1}{\ignorespaces Huffman Coding graph of Speed to number or Threads}}{34}{figure.caption.396}}
\newlabel{fig:CPUThreads}{{6.1}{34}{Huffman Coding graph of Speed to number or Threads}{figure.caption.396}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.1.2}Comparison to standard compression programs}{34}{subsection.397}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.1.3}Comparison of all SKA compression projects}{34}{subsection.400}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.2}{\ignorespaces Graph of Compression times for GPU-Huffman vs Standard algorithms}}{35}{figure.caption.398}}
\newlabel{fig:CompressionTimes}{{6.2}{35}{Graph of Compression times for GPU-Huffman vs Standard algorithms}{figure.caption.398}{}}
\@writefile{toc}{\contentsline {section}{\numberline {6.2}Discussion}{35}{section.404}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.2.1}Feasibility of Huffman Coding in parallel and for SKA}{35}{subsection.405}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.3}{\ignorespaces Graph of Compression ratios for GPU-Huffman vs standard algorithms}}{36}{figure.caption.399}}
\newlabel{fig:CompressionRatios}{{6.3}{36}{Graph of Compression ratios for GPU-Huffman vs standard algorithms}{figure.caption.399}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.4}{\ignorespaces Graph comparing all SKA research Projects with respect to compression speed}}{36}{figure.caption.401}}
\newlabel{fig:SKAComSpeeds}{{6.4}{36}{Graph comparing all SKA research Projects with respect to compression speed}{figure.caption.401}{}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.5}{\ignorespaces Graph comparing all SKA research Projects with respect to decompression speed}}{37}{figure.caption.402}}
\newlabel{fig:SKADecomSpeeds}{{6.5}{37}{Graph comparing all SKA research Projects with respect to decompression speed}{figure.caption.402}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.2.2}Comparison to Standard Compression programs}{37}{subsection.406}}
\@writefile{lof}{\contentsline {figure}{\numberline {6.6}{\ignorespaces Graph of Compression ratios for all SKA research projects}}{38}{figure.caption.403}}
\newlabel{fig:SKACompressionRatios}{{6.6}{38}{Graph of Compression ratios for all SKA research projects}{figure.caption.403}{}}
\@writefile{toc}{\contentsline {subsection}{\numberline {6.2.3}Comparison of SKA compression projects}{38}{subsection.407}}
\@writefile{toc}{\contentsline {chapter}{\numberline {7}Conclusion}{40}{chapter.408}}
\@writefile{lof}{\addvspace {10\p@ }}
\@writefile{lot}{\addvspace {10\p@ }}
\newlabel{Chapter7}{{7}{40}{Conclusion}{chapter.408}{}}
\@writefile{toc}{\vspace  {2em}}
\@writefile{toc}{\vspace  {2em}}
\bibstyle{unsrtnat}
\bibdata{Bibliography}
\bibcite{5365034}{{1}{2009}{{Yang et~al.}}{{Yang, Yang, Wang, and Tseng}}}
\bibcite{954501}{{2}{2001}{{Zhao et~al.}}{{Zhao, Chan, and Gao}}}
\bibcite{5536972}{{3}{2010}{{Ho and Lei}}{{}}}
\bibcite{6530082}{{4}{2013}{{Balid and Abdulwahed}}{{}}}
\bibcite{salomon2004data}{{5}{2004}{{Salomon}}{{}}}
\bibcite{1514415}{{6}{2005}{{Nunez-Yanez and Chouliaras}}{{}}}
\bibcite{6196449}{{7}{2012}{{Chaabouni et~al.}}{{Chaabouni, Fourati, and Bouhlel}}}
\bibcite{613235}{{8}{1997}{{Tang and Szpanskowski}}{{}}}
\bibcite{5974482}{{9}{2011}{{Tang}}{{}}}
\bibcite{488381}{{10}{1996}{{Murashita et~al.}}{{Murashita, Satoh, Okada, and Yoshida}}}
\@writefile{toc}{\contentsline {chapter}{Bibliography}{42}{dummy.412}}
\newlabel{Bibliography}{{6}{42}{Conclusion}{dummy.412}{}}
\bibcite{5164745}{{11}{2009}{{Si et~al.}}{{Si, Yang, Lu, Sun, and Mei}}}
\bibcite{1192978}{{12}{2003}{{Lakhani}}{{}}}
\bibcite{6339599}{{13}{2012}{{Patel et~al.}}{{Patel, Zhang, Mak, Davidson, and Owens}}}
\bibcite{672291}{{14}{1998}{{Kawahara et~al.}}{{Kawahara, Chiu, and Berger}}}
\bibcite{HuffmanCodingSite}{{15}{}{{Seeck}}{{}}}
\bibcite{O'Neil:2011:FDC:1964179.1964189}{{16}{2011}{{O'Neil and Burtscher}}{{}}}
\bibcite{blelloch1990prefix}{{17}{1990}{{Blelloch}}{{}}}
